package com.yuxi.al.leercode;

/**
 * 链表转逆
 * Created by yuxi on 17/2/5.
 */
public class LinkedReserver {
    public static void main(String[] args) {
        Node node1 = new Node(1);
        Node node2 = new Node(2);
        Node node3 = new Node(3);
        Node node4 = new Node(4);
        Node node5 = new Node(5);
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;
        //正序输出
        print(node1);

        //逆序
        Node root = reserver(node1);
        System.out.println("......");
        //逆序输出
        print(root);

    }

    private static void print(Node node1) {
        while (node1 != null) {
            Node tmp = node1;
            System.out.print(tmp.val + "  ");
            node1 = tmp.next;
        }
    }

    private static Node reserver(Node head) {
        if (head == null) {
            return head;
        }
        Node cur = head.next;
        Node pre = head;
        Node next;
        while (cur != null) {
            //找到下一个节点
            next = cur.next;
            //当前节点指向上一个节点
            cur.next = pre;
            //上个节点后移一个
            pre = cur;
            //当前节点后移一个
            cur = next;
        }
        //head节点从头部砍断
        head.next = null;
        //这个时候前一个节点就是最好一个节点
        return pre;
    }

    static class Node {
        public Node(Object val) {
            this.val = val;
        }

        public Object val;
        public Node next;
    }
}
